package com.qfedu.entity.course03;

public class Expression {
    /**
     * c2优先级高于c1 返回 1，相等返回0，低于c1返回-1
     * '+-* /' 四个运算符
     *
     * @param c1
     * @param c2
     * @return
     */
    public static int compare(char c1, char c2) {
        if (c1 == '+' || c1 == '-') {
            if (c2 == '+' || c2 == '-') {
                return 0;
            } else {
                return 1;
            }
        } else {
            if (c2 == '+' || c2 == '-') {
                return -1;
            } else {
                return 0;
            }
        }
    }

    public static String middle2SuffixExpression(String middleExpression) {
        StringBuilder sb = new StringBuilder();
        //设立一个栈，存放运算符，首先栈为空
        LinkedStack<Character> stack = new LinkedStack<>();
        //从左到右扫描中缀表达式
        for (char c : middleExpression.toCharArray()) {
            if (c == ' ') {
                continue;
            } else if (c >= '0' && c <= '9') {
                //- 若遇到操作数，直接输出，并输出空格作为分隔符
                sb.append(c);
                sb.append(' ');
            } else if (c == '(') {
                //- 若遇到左括号，进栈；
                stack.push(c);
            } else if (c == ')') {
                //- 若遇到右括号，则一直退栈输出，直到退到左括号止
                while (stack.get() != null) {
                    char topChar = stack.pop();
                    if (topChar == '(') {
                        break;
                    }
                    sb.append(topChar);
                    sb.append(' ');
                }
            } else {
                // - 若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则出栈输出，并输出空格作分隔符；
                while (!stack.isEmpty()) {
                    char topChar = stack.get();
                    if (topChar == '(') {
                        break;
                    } else if (compare(topChar, c) > 0) {
                        break;
                    } else {
                        topChar = stack.pop();
                        sb.append(topChar);
                        sb.append(' ');
                    }
                }
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
            sb.append(' ');
        }
        return sb.toString();
    }

    public static Double calcSuffix(String suffixExpression) {
        LinkedStack<Double> stack = new LinkedStack<>();
        //从左到右做遍历字符
        for (char c : suffixExpression.toCharArray()) {
            if (c == ' ') {
                continue;
            } else if (c >= '0' && c <= '9') {
                //遇到数字时，将数字压入堆栈
                stack.push((c - '0') * 1.0);
            } else {
                //遇到操作符弹出栈顶的两个数, 此处注意减法、除法的顺序
                Double a = stack.pop();
                Double b = stack.pop();
                //用运算符对它们做相应的计算，结果入栈
                if (c == '+') {
                    stack.push(b + a);
                } else if (c == '-') {
                    stack.push(b - a);
                } else if (c == '*') {
                    stack.push(a * b);
                } else if (c == '/') {
                    stack.push(b / a);
                }
            }
        }
        //最后运算得出的值即为表达式的结果
        Double result = stack.pop();
        return result;
    }

    /**
     * 前缀表达式
     *
     * @param prefixExpression
     * @return
     */
    public static Double calcPrefix(String prefixExpression) {
        LinkedStack<Double> stack = new LinkedStack<>();
        char[] chars = prefixExpression.toCharArray();
        //从右到左遍历字符
        for (int i = chars.length - 1; i >= 0; i--) {
            char c = chars[i];
            if (c == ' ') {
                continue;
            } else if (c >= '0' && c <= '9') {
                //遇到数字时，将数字压入堆栈
                stack.push((c - '0') * 1.0);
            } else {
                //遇到操作符弹出栈顶的两个数
                Double a = stack.pop();
                Double b = stack.pop();
                //用运算符对它们做相应的计算，结果入栈
                if (c == '+') {
                    stack.push(a + b);
                } else if (c == '-') {
                    stack.push(a - b);
                } else if (c == '*') {
                    stack.push(a * b);
                } else if (c == '/') {
                    stack.push(a / b);
                }
            }
        }
        //最后运算得出的值即为表达式的结果
        Double result = stack.pop();
        return result;
    }

    public static void main(String[] args) {
        System.out.println(calcPrefix("-*+ 3 4 5 6"));
        System.out.println(calcSuffix("3 4 + 5 * 6 -"));
        System.out.println(middle2SuffixExpression("(2+1)*((8-2)/(7-4))"));
        System.out.println(middle2SuffixExpression("1+((2+3)*4)-5"));
    }
}
